package syf.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class review {
    public static void main(String[] args) {
//        int[] arr={1,8,10,89,1000,1001,1001,1001,1001,1234};
//
//        System.out.println(binarySearch(arr,0,arr.length-1,1001));
//        List<Integer>list=binarySearchAll(arr,0,arr.length-1,1001);
//        list.sort(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                if(o1>o2)
//                    return 1;
//                return -1;
//            }
//        });
//        System.out.println(list);
        int[] arr={1,8,10,89,1000,1234};
        int res=Fibonacci(arr,0,arr.length-1,10);
        System.out.println(res);
    }
    public static int binarySearch(int[] arr,int left,int right,int val){
        if (right<left) {
            return -1;
        }
        int mid=(right+left)/2;
        int midVal=arr[mid];
        if (val>midVal){//去右边找
            return binarySearch(arr,mid+1,right,val);
        }else if (val<midVal){//去左边找
            return binarySearch(arr,left,mid-1,val);
        }else {//找到了
            return mid;
        }
    }
    public static List<Integer> binarySearchAll(int[] arr, int left, int right,int val){
        List<Integer>list=new ArrayList<>();
        if (right<left) {
            return list;
        }
        int tmp;
        int mid=(right+left)/2;
        int midVal=arr[mid];
        if (val>midVal){//去右边找
            return binarySearchAll(arr,mid+1,right,val);
        }else if (val<midVal){//去左边找
            return binarySearchAll(arr,left,mid-1,val);
        }else {//找到了
            tmp=mid-1;
            while (tmp>=left&&val==arr[tmp]){
                list.add(tmp--);
            }
            list.add(mid);
            tmp=mid+1;
            while (tmp<=right&&val==arr[tmp]){
                list.add(tmp++);
            }
            return list;
        }
    }

    public static int Fibonacci(int[] arr,int left,int right,int val){
        int[] f=pro(20);
        int k=0;
        int mid;
        while (right+1>f[k]-1){
            k++;
        }
        int[] tmp=Arrays.copyOf(arr,f[k]);
        for (int i=arr.length;i<tmp.length;i++){
            tmp[i]=arr[right];
        }
        while (right>=left){
            mid=left+f[k-1]-1;
            if (val>tmp[mid]){
                left=mid+1;
                k-=2;
            } else if (val<tmp[mid]){
                right=mid-1;
                k-=1;
            } else {
                return Math.min(mid, right);
            }
        }
        return -1;
    }
    public static int[] pro(int max){
        int[] arr=new int[max];
        arr[0]=1;
        arr[1]=1;
        int index=2;
        while (index<arr.length){
            arr[index]=arr[index-1]+arr[index-2];
            index++;
        }
        return arr;
    }
}
